package niuke;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author lj
 * @Description: 二叉树的层次遍历-队列
 * @date 2020-10-27 15:03
 * @QQ 851477108
 */


public class erchashu3 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<List<Integer>> levelOrder (TreeNode root) {
        //思路 二叉树的层序遍历 通用思路为使用 队列，利用队列先进先出特点保存每一行的结点，遍历之后出队
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null){
            return lists;
        }

        //存储没层结点队列
        Queue<TreeNode> queueNodes = new LinkedList<>();
        //把当前根节点加入队列
        queueNodes.add(root);
        //遍历队列节点
        while (!queueNodes.isEmpty()){
            //获取当前层级有多少个节点
            int count = queueNodes.size();
            //保存当前遍历节点值得 list
            List<Integer> list = new ArrayList<>();
            //根据队列中的数据 遍历获取节点值
            for (int i = 0; i < count; i++) {
                //当前节点是否有左右子节点
                if (queueNodes.peek().left != null){
                    queueNodes.offer(queueNodes.peek().left);
                }
                if (queueNodes.peek().right != null){
                    queueNodes.offer(queueNodes.peek().right);
                }
                //保存当前节点行元素值数组 并从队列中删除
                list.add(queueNodes.poll().val);
            }
            //保存每一层节点数组
            lists.add(list);
        }
        return lists;
    }
}
